/* 

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false
示例 2:

输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */

// 快慢指针：找到链表中点，然后将后半部分反转，就可以依次比较得出结论了。
// 时间复杂度：O(n)
// 空间复杂度：O(1)

// 递归求反转
var isPalindrome = function (head) {
    const reverse = function (pre, cur) {
        if (!cur) return pre;
        const next = cur.next;
        cur.next = pre;
        return reverse(cur, next);
    }

    let dummyHead = slow = fast = new ListNode();
    dummyHead.next = head;
    // 注意注意，来找中点了, 黄金模板
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    let newStart = slow.next;
    slow.next = null;

    newStart = reverse(null, newStart);

    for (let p = head, newP = newStart; p != null && newP != null; p = p.next, newP = newP.next) {
        if (p.val !== newP.val) return false;
    }

    return true;
};

// 迭代求反转
var isPalindrome = function (head) {
    let reverse = (head) => {
        if (!head || !head.next) return head;
        let pre = null;
        cur = head;
        while (cur) {
            const next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }
    let dummyHead = slow = fast = new ListNode();
    dummyHead.next = head;
    // 注意注意，来找中点了, 黄金模板
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    let next = slow.next;
    slow.next = null;
    let newStart = reverse(next);
    for (let p = head, newP = newStart; p != null && newP != null; p = p.next, newP = newP.next) {
        if (p.val != newP.val) return false;
    }
    return true;
};

// 首尾指针
// 时间复杂度O(n)
// 空间复杂度O(n)
var isPalindrome = function (head) {
    if (!head || !head.next) return true;

    let valArr = [];

    let p = head;

    while (p) {
        valArr.push(p.val);
        p = p.next;
    }

    for (let i = 0, len = valArr.length - 1; i <= Math.floor(len / 2); i++) {
        if (valArr[i] !== valArr[len - i]) return false;
    }

    return true;
};